﻿// 版权所有：
// 文 件  名：QuickSort.cs
// 功能描述：快速排序
// 创建标识：Seven Song(m.sh.lin0328@163.com) 2014/5/1 
// 修改描述：
//----------------------------------------------------------------*/
using System;
using System.Collections.Generic;

namespace MSL.Utility.Sort
{
    /// <summary>
    /// 快速排序
    /// </summary>
    public class QuickSort : SortBase, ISort
    {
        /// <summary>
        /// 倒序排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Desc<T>(IList<T> list) where T : IComparable
        {
            QuickDesc<T>(list, 0, list.Count - 1);
        }
        /// <summary>
        /// 升序排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Asc<T>(IList<T> list) where T : IComparable
        {
            QuickAsc<T>(list, 0, list.Count - 1);
        }

        #region 私有方法

        /// <summary>
        /// 倒序排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        /// <param name="low">开始位置</param>
        /// <param name="high">结束位置</param>
        private void QuickAsc<T>(IList<T> list, int low, int high) where T : IComparable
        {
            if (low >= high) return;
            T temp = list[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (list[j].CompareTo(temp) > 0) j--;
                while (list[i].CompareTo(temp) < 0 && i < j) i++;
                if (i >= j)
                    break;

                Swap(list, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(list, low, j);

            QuickAsc<T>(list, j + 1, high);
            QuickAsc<T>(list, low, j - 1);
        }

        /// <summary>
        /// 升序排序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        /// <param name="low">开始位置</param>
        /// <param name="high">结束位置</param>
        private void QuickDesc<T>(IList<T> list, int low, int high) where T : IComparable
        {
            if (low >= high) return;
            T temp = list[low];
            int i = low + 1, j = high;
            while (true)
            {
                while (list[j].CompareTo(temp) < 0) j--;
                while (list[i].CompareTo(temp) > 0 && i < j) i++;
                if (i >= j)
                    break;

                Swap(list, i, j);
                i++; j--;
            }
            if (j != low)
                Swap(list, low, j);

            QuickDesc<T>(list, j + 1, high);
            QuickDesc<T>(list, low, j - 1);
        }
        #endregion
    }
}
